package Sort_06;

/*
 * @Author 罗
 * @date 2020/3/16 - 5:58 下午
 *
 */
import org.junit.Test;

import java.util.Arrays;


public class Insert_Sort_04 {

    @Test
    public void test_insert() {
        int[] array = {1, 10, 2, 12, 34, 45, 12, 1, 0, 50, -100, -1, 20, 3, 30};
        insertSorting(array);
        System.out.println(Arrays.toString(array));
    }

    /**
     * 插入排序（Insertion Sorting）的基本思想是：
     * 把n个待排序的元素看成为一个有序表和一个无序表，
     * 开始时有序表中只包含一个元素，无序表中包含有n-1个元素，
     * 排序过程中每次从无序表中取出第一个元素，把它的排序码依次与有序表元素的排序码进行比较，
     * 将它插入到有序表中的适当位置，使之成为新的有序表。
     */
    public static void insertSorting(int[] array) {
        /*
            将取出的数再次插入的位置
         */
        int insertIndex = 0;
        /*
         *  取出的数，并用与插入的值
         * */
        int insertValue = 0;

        /*
         * 取出无序表中的元素
         * 因为有序表的长度初始值为1，不能 从有序表中取值，然后将无序表中的所有值插入到有序表中
         * */
        for (int i = 1; i < array.length; i++) {
            /*
             * 将取出的元素顺序与有序表中的元素比较
             * 假设最小值为有序表的最后一个元素array[i-1],i为有序表的长度,array[i]即为无序表的第一个元素
             * 默认插入到有序列表的最后一位
             * */

            insertIndex = i - 1;
            for (int j = i - 1; j >= 0; j--) {
                if (array[i] < array[j]) {
                    /*取出元素比有序表中的元素大
                      从该点开始，到取出元素的位置为止--->
                      有序数列需要往后移动一位的元素的范围 = 有序表的长度 - 取出元素再次插入的位置
                      取出的元素是有序表末尾的相邻下一位
                      将有序表后移一位
                     */
                    insertIndex = j;

                }
            }
            insertValue = array[i];
//              将位置让出
            System.arraycopy(array, insertIndex, array, insertIndex + 1, i - insertIndex);
//                将取出的元素插入移出的空位
            array[insertIndex] = insertValue;

        }
    }


}
